// 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

// 示例:

// 输入: "25525511135"
// 输出: ["255.255.11.135", "255.255.111.35"]

#include <vector>
#include <string>
#include <cstdlib>

using namespace std;

// 递归，分四段，每一段用一位，两位，三位来尝试，分别判断是否合法
class Solution1 {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res{};
        restore(s, 4, "", res);
        return res;
    }
    void restore(string s, int k, string out, vector<string>& res) {
        if (k == 0) {
            if (s.empty()) res.push_back(out);
        } else {
            for (int i{1}; i < 4; ++i) {
                if (s.size() >= i && isValid(s.substr(0, i))) {
                    if (k == 1) restore(s.substr(i), k-1, out + s.substr(0, i), res);
                    else restore(s.substr(i), k-1, out + s.substr(0, i) + ".", res);
                }
            }
        }
    }
    bool isValid(string s) {
        if (s.empty() || s.size() > 3 || (s.size() > 1 && s[0] == '0')) return false;
        int res = atoi(s.c_str());
        return res <= 255 & res >= 0;
    }
};

// 递归，省去isValid函数
class Solution2 {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res{};
        func(s, 0, "", res);
        return res;
    }
    void func(string s, int n, string out, vector<string>& res) {
        if (n == 4) {
            if (s.empty()) res.push_back(out);
        } else {
            for (int k{1}; k < 4; ++k) {
                if (s.size() < k) break;
                int val = atoi(s.substr(0, k).c_str());
                if (val > 255 || k != to_string(val).size()) continue;
                func(s.substr(k), n+1, out + s.substr(0, k) + (n == 3 ? "" : "."), res);
            }
        }
    }
};

class Solution {
private:
    static constexpr int SEG_COUNT{4};
public:
    vector<string> restoreIpAddresses(string s) {
        vector<int> segments(4, 0);
        vector<string> res{};
        dfs(s, 0, 0, segments, res);
        return res;
    }
    void dfs(const string& s, int segId, int segStart, vector<int>& segments, vector<string>& res) {
        // 如果找到了4段IP地址并且遍历完了字符串，就加入结果
        if (segId == SEG_COUNT) {
            if (segStart == s.size()) {
                string ipAddr{};
                for (int i{0}; i < SEG_COUNT; ++i) {
                    ipAddr += to_string(segments[i]);
                    if (i != SEG_COUNT - 1) {
                        ipAddr += ".";
                    }
                }
                res.push_back(move(ipAddr));
            }
            return;
        }
        // 如果没找到四段就已经遍历完字符串，就回溯
        if (segStart == s.size()) {
            return;
        }
        // 如果当前数字是0，这一段只能是0
        if (s[segStart] == '0') {
            segments[segId] = 0;
            dfs(s, segId+1, segStart+1, segments, res);
        }
        // 枚举每一种可能性并递归
        int addr{0};
        for (int segEnd{segStart}; segEnd < s.size(); ++segEnd) {
            addr = addr * 10 + (s[segEnd] - '0');
            if (addr > 0 && addr <= 255) {
                segments[segId] = addr;
                dfs(s, segId+1, segEnd+1, segments, res);
            } else {
                break;
            }
        }
    }
};